package com.mxw.算法之美.a6排序;

/**
 * @author Administrator
 * @create 2024/7/25 14:55
 */
public class a05QuickSort {

    /**
     * 选择0-n之间的任意一个数据作为分区点p，遍历0-n之间的数据，将小于p的数据放到左边，大于p的数据放到右边。遍历完之后，数据被分成三个部分。
     * <p>
     * 递推公式：quickSort(p...r) = quickSort(p...q), quickSort(q+1,r)
     * 递归终止条件：p >= r
     *
     * 最理想的分区点：被分区点分开的两个分区中，数据的数量差不多。
     * 1.三数取中法：从区间的首尾中分别取出一个数。取这三个数的中间值作为分区点
     * 2.随机选择：随机选择一个数作为分区点
     */
    private static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        int p = partition(nums, left, right);

        sort(nums, left, p - 1);
        sort(nums, p + 1, right);
    }

    // 对 nums[lo..hi] 进行切分

    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        // 关于区间的边界控制需格外小心，稍有不慎就会出错
        // 我这里把 i, j 定义为开区间，同时定义：
        // [lo, i) <= pivot；(j, hi] > pivot
        // 之后都要正确维护这个边界区间的定义
        int i = left + 1, j = right;
        // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
        while (i <= j) {
            while (i < right && nums[i] <= pivot) {
                i++;
                // 此 while 结束时恰好 nums[i] > pivot
            }
            while (j > left && nums[j] > pivot) {
                j--;
                // 此 while 结束时恰好 nums[j] <= pivot
            }
            // 此时 [lo, i) <= pivot && (j, hi] > pivot

            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        // 将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        swap(nums, left, j);
        return j;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
